package yijy.arrayExamples;

import java.util.Arrays;

/**
 * Created by yijy on 2017/8/18.
 * 随便输入一个数组，截取其中紧邻的元素作为子数组(长度最小为1)，并使得子数组中求和值最大
 */
public class MaxSumSubArray {
    public static void main(String[] args) {
        int[] arr = {3,1,-3,4,-1,2,1,-5,4};
        maxSum(arr);
        int max =maxSubArray(arr);
        System.out.println(max);
    }
    //遍历截取数组，分别截取的子数组求和，比较值最大的数组
    public static void maxSum(int[] arr){
        int max=0;
        int low=0 ;
        int height=0;
        if(arr.length>=1){
            for(int i=0;i<arr.length;i++){
                int sum=0;
                for(int j=i;j<arr.length;j++){
                    sum += arr[j];
                    if(max<=sum){
                        max = sum;
                        low = i;
                        height=j;
                    }
                }
            }
            int[] newArr = new int[height-low+1];
            System.arraycopy(arr,low,newArr,0,height-low+1);
            System.out.println(Arrays.toString(newArr)+"    max:"+max);
        }
    }

    public static int maxSubArray(int[] A) {
        int max = Integer.MIN_VALUE, sum = 0;
        System.out.println("min:"+max);
        for (int i = 0; i < A.length; i++) {
            if (sum < 0)
                sum = A[i];
            else
                sum += A[i];
            if (sum > max)
                max = sum;
        }
        return max;
    }

}
